package main

import (
	"fmt"
	"math"
)

/*
getSize()  返回堆的长度
isEmpty()  判断数组
parent() 返回父节点的下标
leftChild() 返回当前节点的左孩子
rightChild() 返回当前节点的右孩子
heapInsert()heapSize加1，把新数放到堆尾的节点上。和父节点比较，如果父节点比该数小就交换，以此类推，直至父节点比其大或者没有父节点了。
heapify()如何取出大根堆的头结点？取出头节点，把最后一个节点的数放在头结点上，heapSize减1。然后把头结点的数和两个子节点中最大的数比较，
比较大子节点还大就交换位置，以此操作，直至没有子节点或者比子节点都小。这个过程叫做heapify.
*/
func main() {
	//arr := []int{3, 5, 1, 4, 2} // 定义一个待排序的数组
	//fmt.Println("The original array is:", arr)
	//arr = HeapSort(arr) // 调 用堆排序方法对数组进行排序
	//fmt.Println("The sorted array is:", arr)
	ints := []int{4, 5, 3, 1, 2}
	SortAlmostOrderedArrays(ints, 2)
	fmt.Println(ints)

}
func SortAlmostOrderedArrays(arr []int, k int) { //对于接近有序的数组排序，当前数和他对应的位置前后不超过k
	/*
		思路就是创建一个堆栈其大小要保持k-1
		如果是降序排序大根堆的最上面的节点就是最前面要排序的位置
		然后要输出一个位置就弹出一个最大数再从尾部加上一个数也就是必须要两个指针一个指针指向堆吞到哪个数，另一个指针指向数组将要排序的位置
		堆弹出一个位置的同时将其输出到要将要排序的位置并且让其往下一位然后加上将要吞的数的位置同时判断后面将要吞的位置是否超出数组长度
		如果超出就只实现弹出操作
	*/
	if arr == nil || len(arr) < 2 {
		return

	}
	index := int(math.Min(float64(len(arr)-1), float64(k)))
	newHeap := NewHeap()
	for i := 0; i <= index; i++ {

		newHeap.add(arr[i])
	}
	i := 0 //数组将要排序的位置
	index++
	for ; i < len(arr); i++ {
		if index < len(arr) {
			arr[i] = newHeap.poll()
			newHeap.add(arr[index])
			index++
		} else {
			arr[i] = newHeap.poll()
		}
	}
}
func (h *Heap) heapSort2() {
	//这个时自下向上的构建堆的堆排序方法使用之前不要调用Newheap来创建
	//而是直接通过对象创建给他无序得数组和对应的堆长度这两个属性再去电泳heapSort2来完成这一操作
	/*
		heap := Heap{
				array:    []int{1, 4, 5, 3, 1, 4, 5, 7, 8},
				heapSize: 9,
			}
			heap.heapSort2()
			fmt.Println(heap)
	*/
	if h.array == nil || len(h.array) < 2 {
		return
	}

	for i := len(h.array) - 1; i >= 0; i-- {
		h.heapTidy(i)
	}

	for true {
		if h.heapSize > 0 {
			h.heapSize--
			h.array[0], h.array[h.heapSize] = h.array[h.heapSize], h.array[0]

			h.heapTidy(0)
		} else {
			break
		}
	}

}

type Heap struct {
	array    []int
	heapSize int
}

func NewHeap() *Heap {
	return &Heap{
		array:    make([]int, 50),
		heapSize: 0,
	}
}
func (h Heap) getSize() int {
	return h.heapSize
}
func (h *Heap) isEmpty() bool {
	if h.heapSize == 0 {
		return true
	} else {
		return false
	}
}

func (h *Heap) parent(index int) int {
	parentIndex := (index - 1) / 2
	if parentIndex >= 0 {
		return parentIndex
	} else {
		return -1
	}
}
func (h *Heap) leftChild(index int) int {
	if index >= 0 {
		return index*2 + 1
	} else {
		return -1
	}
}

func (h *Heap) rightChild(index int) int {
	if index >= 0 {
		return index*2 + 2
	} else {
		return -1
	}
}

func (h *Heap) heapInsert(index int) {
	if h.parent(index) >= 0 {
		for h.array[index] > h.array[h.parent(index)] {
			if h.parent(index) >= 0 {
				h.array[index], h.array[h.parent(index)] = h.array[h.parent(index)], h.array[index]
				index = h.parent(index)
			}
		}
	}

}

func (h *Heap) heapTidy(index int) {
	leftChild := h.leftChild(index)

	for leftChild < h.heapSize {
		max := leftChild
		if leftChild+1 < h.heapSize && h.array[leftChild+1] > h.array[leftChild] {
			max = leftChild + 1
		}
		if h.array[max] < h.array[index] {
			max = index
		}
		if max == index {
			break
		}

		h.array[max], h.array[index] = h.array[index], h.array[max]
		index = max
		leftChild = index*2 + 1
	}
}

func (h *Heap) add(value int) {

	h.array[h.heapSize] = value
	h.heapInsert(h.heapSize)
	h.heapSize++

}

func (h *Heap) heapSort() {
	if h.array == nil || len(h.array) < 2 {
		return
	}
	for true {
		if h.heapSize > 0 {
			h.heapSize--
			h.array[0], h.array[h.heapSize] = h.array[h.heapSize], h.array[0]

			h.heapTidy(0)
		} else {
			break
		}
	}

}

func (h *Heap) poll() int {
	max := h.array[0]

	h.array[0], h.array[h.heapSize-1] = h.array[h.heapSize-1], h.array[0]
	h.heapSize--
	h.heapTidy(0)
	return max
}

func (h *Heap) changeIndexValue(index, value int) {

	h.array[index] = value
	h.heapInsert(index)
	h.heapTidy(index)
}
